package algorithm.dp;

import java.util.ArrayList;
import java.util.List;

public class Coin {
    int[] nums = new int[] {1, 3, 5};

    public int getMin(int target) {
        if (target <= 0) {
            return 0;
        }

        int[] dp = new int[target + 1];
        for(int i = 1; i <= target; i++) {
            //我们假设存在1元的硬币那么i元最多只需要i枚1元硬币，当然最好设置dp[i]等于无穷大
            dp[i] = i;
        }

        for(int i = 1; i <= target; i++){
            for(int j = 0; j < nums.length; j++) {
                int num = nums[j];
                if(i >= num && dp[i - num] + 1 < dp[i]){
                    dp[i] = dp[i- num] + 1;
                }
            }
        }

        return dp[target];
    }
}
